import java.util.*;

/**
 * 241. 为运算表达式设计优先级
 * https://leetcode-cn.com/problems/different-ways-to-add-parentheses/
 */
public class Solutions_241 {
    public static void main(String[] args) {
//        String input = "11";  // output: {11}
//        String input = "-13";  // output: {-13}
//        String input = "10+5";  // output: {15}

//        String input = "2-1-1";  // output: {0, 2}
        // 2 - (1 - 1) = 2，(2 - 1) - 1 = 0

        String input = "2*3-4*5";  // output: {-34, -14, -10, -10, 10}
        // 2 * ((3 - 4) * 5) = -10，2 * (3 - (4 * 5)) = -34，...

        List<Integer> result = diffWaysToCompute(input);
        System.out.println(result);
    }

    // 因存在大量的重复递归，采用记忆化递归进行优化
    // 对每次递归的字符串及其能够计算得到的结果，保存到 map 中
    private static Map<String, List<Integer>> strMap = new HashMap<>();
    public static List<Integer> diffWaysToCompute(String input) {
        return diffWaysToCompute(input, 0, input.length() - 1);
    }

    public static List<Integer> diffWaysToCompute(String input, int start, int end) {
        List<Integer> res = new ArrayList<>();
        if (start > end) {
            return res;
        }
        if (start == end) {
            res.add(input.charAt(start) - '0');
            return res;
        }
        if (strMap.containsKey(input.substring(start, end + 1))) {
            // 已经计算过，直接获取结果
            return strMap.get(input.substring(start, end + 1));
        }
        // 左边全部的计算数与右边全部的计算数两两计算
        for (int i = start; i <= end; i++) {
            char c = input.charAt(i);
            if (!Character.isDigit(c)) {
                // 是运算符
                List<Integer> leftRes = diffWaysToCompute(input, start, i - 1);
                List<Integer> rightRes = diffWaysToCompute(input, i + 1, end);

                for (int left : leftRes) {
                    for (int right : rightRes) {
                        if (c == '+') {
                            res.add(left + right);
                        } else if (c == '-') {
                            res.add(left - right);
                        } else if (c == '*') {
                            res.add(left * right);
                        }
                    }
                }
                // 记忆化
                strMap.put(input.substring(start, end + 1), res);
            }
        }
        if (res.size() == 0 && input.length() > 0) {
            // [start, end] 索引上的子串中，没有符号的情况，全部为数字
            res.add(Integer.valueOf(input.substring(start, end + 1)));
        }
        return res;
    }
}
